package com.leetcode.weekly.contest.no233th;

/**
 * @author 覃国强
 * @date 2021-03-21 11:25
 */
public class A03_有界数组中指定下标处的最大值 {

  public static void main(String[] args) {
    Solution solution = new Solution();
    int n = 2;
    int index = 1;
    int maxSum = 589774098;
    int maxValue = solution.maxValue(n, index, maxSum);
    System.out.println(maxValue);
  }

  static
  class Solution {
    public int maxValue(int n, int index, int maxSum) {
      if (maxSum == n) {
        return 1;
      }

      int diff = maxSum - n;

      if (index == 0 || index == n - 1) {
        // 向一边延伸
        int result = 1;
        int i = 1;
        while (i < n) {
          diff -= i;
          if (diff < 0) {
            diff = 0;
            break;
          }
          ++result;
          ++i;
        }
        result += diff / n;
        return result;
      } else {
        // 向两边延伸
        int result = 1;
        int left = 0;
        int right = 0;
        int middle = 1;

        int leftMax = index;
        int rightMax = n - index - 1;

        while (left < leftMax || right < rightMax) {
          diff -= (middle + left + right);
          if (diff < 0) {
            diff = 0;
            break;
          }
          ++result;
          if (left < leftMax) {
            ++left;
          }
          if (right < rightMax) {
            ++right;
          }
        }
        result = result + diff / n;
        return result;
      }
    }
  }

}
